#include <iostream>

enum ColorType {
  RED,
  BLACK
};

template<class T = int>
class RbNode : public BitNode<T> {
  public:
    explicit RbNode(T _data) : BitNode<T>(_data), color(RED) {}
    RbNode(T _data, ColorType _color) : BitNode<T>(_data), color(_color) {}
    virtual ~RbNode() = default;

  public:
    ColorType color;
};

template<class T = int>
void setColor(BitNode<T>* node, ColorType col)
{
  if (node == nullptr) {
    return;
  }

  dynamic_cast<RbNode<T>*>(node)->color = col;
}

template<class T = int>
ColorType getColor(BitNode<T>* node)
{
  if (node == nullptr) {
    return BLACK;
  }

  return dynamic_cast<RbNode<T>*>(node)->color;
}

template<class T = int>
int getHightRb(RbNode<T>* root)
{
  if (root == nullptr) {
    return 1;  // 空节点黑高为1
  }

  int lH = getHightRb(dynamic_cast<RbNode<T>*>(root->lchild));
  int rH = getHightRb(dynamic_cast<RbNode<T>*>(root->rchild));

  return (lH > rH ? lH : rH) + ((root->color == BLACK) ? 1 : 0);
}

// 要求节点非空，且其兄弟为黑色非空节点，即节点不与父节点组合成3、4节点
template<class T = int>
char nodeWeight(RbNode<T>* node)
{
  if (getColor(node) == RED) {
    return 3;
  }

  if ((getColor(node->lchild) == BLACK) && (getColor(node->rchild) == BLACK)) {
    return 2;
  }

  if ((getColor(node->lchild) == RED) && (getColor(node->rchild) == RED)) {
    return 4;
  }

  return 3;
}

